{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #求根节点到叶节点数字之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #求根节点到叶节点数字之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的根节点 <code>root</code> ，树中每个节点都存放有一个 <code>0</code> 到 <code>9</code> 之间的数字。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>每条从根节点到叶节点的路径都代表一个数字：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，从根节点到叶节点的路径 <code>1 -&gt; 2 -&gt; 3</code> 表示数字 <code>123</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>计算从根节点到叶节点生成的 <strong>所有数字之和</strong> 。</p>\n",
    "\n",
    "<p><strong>叶节点</strong> 是指没有子节点的节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/num1tree.jpg\" style=\"width: 212px; height: 182px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3]\n",
    "<strong>输出：</strong>25\n",
    "<strong>解释：</strong>\n",
    "从根到叶子节点路径 <code>1-&gt;2</code> 代表数字 <code>12</code>\n",
    "从根到叶子节点路径 <code>1-&gt;3</code> 代表数字 <code>13</code>\n",
    "因此，数字总和 = 12 + 13 = <code>25</code></pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/num2tree.jpg\" style=\"width: 292px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,9,0,5,1]\n",
    "<strong>输出：</strong>1026\n",
    "<strong>解释：</strong>\n",
    "从根到叶子节点路径 <code>4-&gt;9-&gt;5</code> 代表数字 495\n",
    "从根到叶子节点路径 <code>4-&gt;9-&gt;1</code> 代表数字 491\n",
    "从根到叶子节点路径 <code>4-&gt;0</code> 代表数字 40\n",
    "因此，数字总和 = 495 + 491 + 40 = <code>1026</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[1, 1000]</code> 内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 9</code></li>\n",
    "\t<li>树的深度不超过 <code>10</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 129&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/\">https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [3Etpl5](https://leetcode.cn/problems/3Etpl5/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [3Etpl5](https://leetcode.cn/problems/3Etpl5/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[4,9,0,5,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = \"\"\n",
    "        self.res = 0\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    def traverse(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.path +=str(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            self.res+=int(self.path)\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        self.path = self.path[:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # 回溯法\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.sumn = 0\n",
    "        self.num = 0\n",
    "        self.dfs(root)\n",
    "        return self.sumn\n",
    "    \n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return\n",
    "        self.num = self.num*10 + node.val\n",
    "        if not node.left and not node.right:\n",
    "            self.sumn += self.num\n",
    "        self.dfs(node.left)\n",
    "        self.dfs(node.right)\n",
    "        self.num = (self.num - node.val) // 10\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        al = []\n",
    "        tem = ''\n",
    "        def dfs(root, tem, al):\n",
    "            if root:\n",
    "                tem += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                al.append(tem)\n",
    "            else:\n",
    "                if root.left:\n",
    "                    dfs(root.left, tem, al)\n",
    "                if root.right:\n",
    "                    dfs(root.right, tem, al)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        dfs(root, tem, al)\n",
    "        res = 0\n",
    "        for i in al:\n",
    "            res += int(i)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        sumn = 0\n",
    "        que = [root]\n",
    "        while que:\n",
    "            if not que[0].left and not que[0].right:\n",
    "                sumn += que[0].val\n",
    "            if que[0].left:\n",
    "                que.append(que[0].left)\n",
    "                que[0].left.val = 10*que[0].val + que[0].left.val\n",
    "            if que[0].right:\n",
    "                que.append(que[0].right)\n",
    "                que[0].right.val = 10*que[0].val + que[0].right.val\n",
    "            que.pop(0)\n",
    "        return sumn\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def DFS(self,root,number):\n",
    "        if root==None:\n",
    "            return number\n",
    "        \n",
    "        if root.left==None and root.right==None:\n",
    "            return number*10+root.val\n",
    "        \n",
    "        if root.left:\n",
    "            res1= self.DFS(root.left,number*10+root.val)\n",
    "        else:\n",
    "            res1 = 0\n",
    "            \n",
    "        if root.right:\n",
    "            res2 = self.DFS(root.right,number*10+root.val)\n",
    "        else:\n",
    "            res2 = 0\n",
    "            \n",
    "        return res1+res2\n",
    "    def sumNumbers(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.DFS(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def helper(root, res):\n",
    "            if not root:\n",
    "                return 0\n",
    "            res = res*10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return res\n",
    "            return helper(root.left, res) + helper(root.right, res)\n",
    "        return helper(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.sum=0\n",
    "        self.num=0\n",
    "        def back(root):\n",
    "            if not root:\n",
    "                return\n",
    "            self.num = self.num * 10+root.val\n",
    "            if root.left==None and root.right==None:\n",
    "                self.sum+=self.num\n",
    "            back(root.left)\n",
    "            back(root.right)\n",
    "            self.num = (self.num-root.val)//10\n",
    "        back(root)\n",
    "        return self.sum\n",
    "        # self.sum=0\n",
    "        # def dfs(root, num):\n",
    "        #     if not root:\n",
    "        #         return\n",
    "        #     num = num * 10 + root.val\n",
    "        #     if not root.left and not root.right:\n",
    "        #         self.sum += num\n",
    "        #     dfs(root.left,num)\n",
    "        #     dfs(root.right,num)\n",
    "        # dfs(root,0)\n",
    "        # return self.sum\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            return self.findPath(root, 0)\n",
    "\n",
    "    def findPath(self, root, temp):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            temp = temp*10 + root.val\n",
    "            if root.left is None and root.right is None:\n",
    "                return temp\n",
    "            else:\n",
    "                return self.findPath(root.left, temp) + self.findPath(root.right, temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def traverse(root, trace):\n",
    "            if not root:\n",
    "                return 0\n",
    "            new_trace = trace * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return new_trace            \n",
    "            return traverse(root.left, new_trace) + traverse(root.right, new_trace)\n",
    "        \n",
    "        return traverse(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(node, val):\n",
    "            if not node: return 0\n",
    "            val = val * 10 + node.val\n",
    "            if not (node.left or node.right):\n",
    "                return val\n",
    "            return dfs(node.left, val) + dfs(node.right, val)\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        return self.search(root, 0)\n",
    "        \n",
    "    def search(self, node, nowSum):\n",
    "        if not node:\n",
    "            return 0\n",
    "        nowSum=nowSum*10+node.val\n",
    "        if not node.left and not node.right:\n",
    "            return nowSum\n",
    "        left=self.search(node.left, nowSum)\n",
    "        right=self.search(node.right, nowSum)\n",
    "        return left+right\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root: TreeNode, prevTotal: int) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            total = prevTotal * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return total\n",
    "            else:\n",
    "                return dfs(root.left, total) + dfs(root.right, total)\n",
    "\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            return self.findPath(root, 0)\n",
    "\n",
    "    def findPath(self, root, temp):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            temp = temp*10 + root.val\n",
    "            if root.left is None and root.right is None:\n",
    "                return temp\n",
    "            else:\n",
    "                return self.findPath(root.left, temp) + self.findPath(root.right, temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(node: TreeNode, prevTotal: int)->int:\n",
    "            if not node: return 0\n",
    "            total = prevTotal * 10 + node.val\n",
    "            if not node.left and not node.right:\n",
    "                return total\n",
    "            else:\n",
    "                return dfs(node.left,total)+dfs(node.right,total)\n",
    "        \n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root, val) -> int:\n",
    "            val = val * 10 + root.val\n",
    "            if root.left == None and root.right == None:\n",
    "                nonlocal ans\n",
    "                ans += val\n",
    "            else:\n",
    "                if root.left: dfs(root.left, val)\n",
    "                if root.right: dfs(root.right, val)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        return self.dfs(root, 0)\n",
    "    \n",
    "    def dfs(self, root, val):\n",
    "        if not root:\n",
    "            return 0\n",
    "        val = val * 10 + root.val\n",
    "        if not root.left and not root.right:\n",
    "            return val\n",
    "        return self.dfs(root.left, val) + self.dfs(root.right, val) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        def recurse(node, load):\n",
    "            nonlocal res\n",
    "            if node == None:\n",
    "                tmp = 0\n",
    "                for v in load:\n",
    "                    tmp = tmp*10 +v\n",
    "                res +=tmp\n",
    "                return\n",
    "            v =node.val\n",
    "            if not node.left and not node.right:\n",
    "                t = load + [v]\n",
    "                tmp = 0\n",
    "                for v in t:\n",
    "                    tmp = tmp*10 +v\n",
    "                res +=tmp\n",
    "                return\n",
    "            if node.left:\n",
    "                recurse(node.left, load +[v])\n",
    "            if node.right:\n",
    "                recurse(node.right, load + [v])\n",
    "        recurse(root, [])\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root,presum):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            s = 10*presum+root.val\n",
    "            if root.left is None and root.right is None:\n",
    "                return s\n",
    "            return dfs(root.left,s)+dfs(root.right,s)\n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        ans=[]\n",
    "        def bl(p,t):\n",
    "            t=t+str(p.val)\n",
    "            if p.left:\n",
    "                bl(p.left,t)\n",
    "            if p.right:\n",
    "                bl(p.right,t)\n",
    "            if p.left is None and p.right is None:\n",
    "                ans.append(t)\n",
    "                return\n",
    "        if root is None: return 0\n",
    "        bl(root,'')\n",
    "        # print(ans)\n",
    "        res=0\n",
    "        for i in ans:\n",
    "            res+=int(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        # 每一次 dfs 形成一个数值\n",
    "        # 数值跟层次有关系,层次是递增的，没法形成有效的数计算，需要保存数值\n",
    "        # 再将数值累加\n",
    "        isLeafNode = lambda node: not node.left and not node.right\n",
    "\n",
    "        def dfs(node: TreeNode, prevTotal:int) -> int:\n",
    "\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            # 不加这个条件的话，就会导致两次计算\n",
    "            if isLeafNode(node):\n",
    "                return prevTotal * 10 + node.val\n",
    "            \n",
    "            left = dfs(node.left, prevTotal * 10 + node.val)\n",
    "            right = dfs(node.right, prevTotal * 10 + node.val)\n",
    "            return left + right \n",
    "\n",
    "        return dfs(root, 0) if root else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(root, val):\n",
    "            if not root:\n",
    "                return\n",
    "            root.val += val * 10\n",
    "            dfs(root.left, root.val)\n",
    "            dfs(root.right, root.val)\n",
    "            if not root.left and not root.right:\n",
    "                self.ans += root.val\n",
    "        dfs(root, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        def dfs(node: TreeNode, cur: int):\n",
    "            cur = cur * 10 + node.val\n",
    "            if node.left:\n",
    "                dfs(node.left, cur)\n",
    "            if node.right:\n",
    "                dfs(node.right, cur)\n",
    "            if not node.left and not node.right:\n",
    "                nonlocal ans\n",
    "                ans += cur\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if not node.left and not node.right:\n",
    "                res += node.val\n",
    "                return [1]\n",
    "            ret = []\n",
    "            if node.left:\n",
    "                lefts = dfs(node.left)\n",
    "                for left in lefts:\n",
    "                    res += pow(10,left)*node.val\n",
    "                    ret.append(left+1)\n",
    "            if node.right:\n",
    "                rights = dfs(node.right)\n",
    "                for right in rights:\n",
    "                    res += pow(10,right)*node.val\n",
    "                    ret.append(right+1)\n",
    "            return ret\n",
    "        rets = dfs(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def helper(root, cur_sum):\n",
    "            if not root:\n",
    "                return 0\n",
    "            cur_sum = cur_sum*10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return cur_sum\n",
    "            return helper(root.left, cur_sum) + helper(root.right, cur_sum)\n",
    "        return helper(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(node, val):\n",
    "            if not node: return 0\n",
    "            val = val * 10 + node.val\n",
    "            if not node.left and not node.right:\n",
    "                return val\n",
    "            return dfs(node.left, val) + dfs(node.right, val)\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def preorder(root, preS):\n",
    "            if not root:\n",
    "                return 0\n",
    "            s  = preS * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return s\n",
    "            else: return preorder(root.left, s)  + preorder(root.right, s)\n",
    "        return preorder(root, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "    \n",
    "        res = 0\n",
    "        def dfs(root, num):\n",
    "            nonlocal res\n",
    "            if not root: return \n",
    "            if not root.left and not root.right:\n",
    "                res += num \n",
    "                return\n",
    "            if root.left:\n",
    "                dfs(root.left, num * 10 + root.left.val)\n",
    "            if root.right:\n",
    "                dfs(root.right, num * 10 + root.right.val)\n",
    "        dfs(root, root.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.num=0\n",
    "        def dfs(r:TreeNode,temp:int):\n",
    "            temp=temp*10+r.val\n",
    "            if not r.left and not r.right:\n",
    "                self.num+=temp\n",
    "                return\n",
    "            if r.left:dfs(r.left,temp)\n",
    "            if r.right:dfs(r.right,temp)\n",
    "        dfs(root,0)\n",
    "        return self.num\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.res, self.path_sum = 0, 0\n",
    "        def dfs(root):\n",
    "            self.path_sum = self.path_sum * 10 + root.val\n",
    "\n",
    "            if root.left:\n",
    "                dfs(root.left)\n",
    "            if root.right:\n",
    "                dfs(root.right)\n",
    "            elif not root.left:\n",
    "                self.res += self.path_sum\n",
    "            \n",
    "            self.path_sum = self.path_sum // 10\n",
    "            return\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(node, total):\n",
    "            if not node:\n",
    "                return 0\n",
    "            tmp = total * 10 + node.val\n",
    "            left = dfs(node.left, tmp)\n",
    "            right = dfs(node.right, tmp)\n",
    "            if not left and not right:\n",
    "                return tmp\n",
    "            return left + right\n",
    "\n",
    "        return dfs(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "\n",
    "        if( not root):\n",
    "            return 0\n",
    "        self.sum1 = 0\n",
    "        def dfs(root, cur):\n",
    "            if(not root):\n",
    "                #self.sum1 = self.sum1 + (int)(cur)\n",
    "                return\n",
    "            if(not root.left and not root.right):\n",
    "                self.sum1 = self.sum1 + (int)(cur + str(root.val))\n",
    "                return \n",
    "            dfs(root.left, cur + str(root.val))\n",
    "            dfs(root.right,cur+str(root.val))\n",
    "\n",
    "        dfs(root, \"\")\n",
    "        return self.sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root, prevTotal) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            total = prevTotal * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return total\n",
    "            else:\n",
    "                return dfs(root.left, total) + dfs(root.right, total)\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        if root is None:\n",
    "            return res\n",
    "\n",
    "        def dfs(root, pathSum):\n",
    "            nonlocal res\n",
    "            # 只遍历非空节点\n",
    "            if root.left is None and root.right is None:\n",
    "                res += pathSum * 10 + root.val\n",
    "                return\n",
    "\n",
    "            pathSum = pathSum * 10 + root.val\n",
    "            if root.left is not None:\n",
    "                dfs(root.left, pathSum)\n",
    "            if root.right is not None:\n",
    "                dfs(root.right, pathSum)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.stack = list()\n",
    "\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        return self.traverse(root)\n",
    "\n",
    "    def traverse(self, curr: TreeNode) -> int:\n",
    "        result = 0\n",
    "        if curr is None:\n",
    "            return 0\n",
    "        self.stack.append(curr.val)\n",
    "        if curr.left is None and curr.right is None:\n",
    "            ret = 0\n",
    "            for i in self.stack:\n",
    "                ret = ret * 10 + i\n",
    "            self.stack = self.stack[:-1]\n",
    "            return ret\n",
    "        if curr.left:\n",
    "            result += self.traverse(curr.left)\n",
    "        if curr.right:\n",
    "            result += self.traverse(curr.right)\n",
    "        self.stack = self.stack[:-1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node, cur_val=0):\n",
    "        if not node:\n",
    "            return\n",
    "        cur_val =  10 * cur_val + node.val\n",
    "        if not node.left and not node.right:\n",
    "            self.sum += cur_val\n",
    "            return\n",
    "        self.dfs(node.left, cur_val)\n",
    "        self.dfs(node.right, cur_val)\n",
    "\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.sum = 0\n",
    "        self.dfs(root, 0)\n",
    "        return self.sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def func(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            else:\n",
    "                res=[]\n",
    "                l=func(root.left)\n",
    "                r=func(root.right)\n",
    "                if l:\n",
    "                    for i in l:\n",
    "                        res.append('{}'.format(root.val)+i)\n",
    "                if r:\n",
    "                    for i in r:\n",
    "                        res.append('{}'.format(root.val)+i)\n",
    "                if not l and not r:\n",
    "                    res.append('{}'.format(root.val))\n",
    "                return res\n",
    "        res=func(root)\n",
    "        r=0\n",
    "        for i in res:\n",
    "            r+=int(i)\n",
    "        return r\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.sum_ = 0\n",
    "        self.back(root,0)\n",
    "        return self.sum_\n",
    "    def back(self,root,path):\n",
    "        if not root: \n",
    "            return path\n",
    "        path = path*10+root.val\n",
    "        if not root.left and not root.right: \n",
    "            self.sum_+=path\n",
    "            return (path-root.val)//10\n",
    "\n",
    "        path = self.back(root.left,path)\n",
    "        path = self.back(root.right,path)\n",
    "\n",
    "        return (path-root.val)//10\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.sum=0\n",
    "        def dfs(root, num):\n",
    "            if not root:\n",
    "                return\n",
    "            num = num * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                self.sum += num\n",
    "            dfs(root.left,num)\n",
    "            dfs(root.right,num)\n",
    "        dfs(root,0)\n",
    "        return self.sum\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "\n",
    "        def dfs(root,cur):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if not root.left and not root.right:\n",
    "                return cur*10+root.val\n",
    "\n",
    "            return  dfs(root.left,cur*10+root.val)+dfs(root.right,cur*10+root.val)\n",
    "        \n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    res = 0\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        def dfs(root,base):\n",
    "            if not root:\n",
    "                return\n",
    "            base  = base * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                self.res += base \n",
    "                base = 0 # 抵达叶子结点进行roll back\n",
    "            dfs(root.left,base)\n",
    "            dfs(root.right,base)\n",
    "        dfs(root,0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "\n",
    "        if root is None:\n",
    "            return 0\n",
    "        node_list = [root]\n",
    "        result_list = [root.val]\n",
    "        count = 1\n",
    "        next_layer_count = 0\n",
    "        result = 0\n",
    "        while len(node_list)>0 and count > 0:\n",
    "            node = node_list.pop()\n",
    "            node_new_val = result_list.pop()\n",
    "            count -=1\n",
    "            if node.left is not None:\n",
    "                new_val = node_new_val*10 + node.left.val\n",
    "                next_layer_count +=1\n",
    "                result_list.append(new_val)\n",
    "                node_list.append(node.left)\n",
    "            if node.right is not None:\n",
    "                new_val = node_new_val*10 + node.right.val\n",
    "                next_layer_count +=1\n",
    "                result_list.append(new_val)\n",
    "                node_list.append(node.right)\n",
    "            # 叶子节点\n",
    "            if node.left is None and node.right is None:\n",
    "                result+=node_new_val\n",
    "            # 更新层信息\n",
    "            if next_layer_count>0 and count==0:\n",
    "                count = next_layer_count\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.sum_numbers(root, 0)\n",
    "\n",
    "    def sum_numbers(self, root: Optional[TreeNode], num: int) -> int:\n",
    "        num = num * 10 + root.val\n",
    "        if root.left is None and root.right is None:\n",
    "            return num\n",
    "        left_num = 0\n",
    "        if root.left is not None:\n",
    "            left_num = self.sum_numbers(root.left, num)\n",
    "        right_num = 0\n",
    "        if root.right is not None:\n",
    "            right_num = self.sum_numbers(root.right, num)\n",
    "        return left_num + right_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def helper(node, path):\n",
    "            if not node:\n",
    "                return\n",
    "            path.append(node.val)\n",
    "            if not node.left and not node.right:\n",
    "                res.append(int(\"\".join(map(str, path))))\n",
    "            helper(node.left, path)\n",
    "            helper(node.right, path)\n",
    "            path.pop()\n",
    "\n",
    "        helper(root, [])\n",
    "        return sum(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.dfs(root, 0)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self, node, cnt):\n",
    "        if not node:\n",
    "            return 0\n",
    "        original = cnt\n",
    "        cnt = 10 * cnt + node.val\n",
    "        if not node.left and not node.right:\n",
    "            self.res += cnt\n",
    "            return\n",
    "        self.dfs(node.left, cnt)\n",
    "        self.dfs(node.right, cnt)\n",
    "        cnt = original"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root: TreeNode, prevTotal: int) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            total = prevTotal * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return total\n",
    "            else:\n",
    "                return dfs(root.left, total) + dfs(root.right, total)\n",
    "\n",
    "        return dfs(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root: return 0\n",
    "        ans, p = [], [(root, str(root.val))]\n",
    "        while p:\n",
    "            tmp, s = p.pop(0)\n",
    "            if tmp.left: p.append((tmp.left, s+str(tmp.left.val)))\n",
    "            if tmp.right: p.append((tmp.right, s+str(tmp.right.val)))\n",
    "            if tmp.left==None and tmp.right==None: ans.append(s)\n",
    "        return sum(map(int, ans))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return root.val\n",
    "        if not root.left:\n",
    "            root.right.val += 10*root.val\n",
    "            return self.sumNumbers(root.right)\n",
    "        if not root.right:\n",
    "            root.left.val += 10*root.val\n",
    "            return self.sumNumbers(root.left)\n",
    "        root.left.val += 10*root.val\n",
    "        root.right.val += 10*root.val\n",
    "        return self.sumNumbers(root.left)+self.sumNumbers(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "    \n",
    "        self.res = 0\n",
    "        def dfs(root, num):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                self.res += num \n",
    "                return\n",
    "            if root.left:\n",
    "                dfs(root.left, num * 10 + root.left.val)\n",
    "            if root.right:\n",
    "                dfs(root.right, num * 10 + root.right.val)\n",
    "                \n",
    "        dfs(root, root.val)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(root, pre):\n",
    "            nonlocal cnt\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                cnt += pre * 10 + root.val\n",
    "                return\n",
    "                \n",
    "            dfs(root.left, pre * 10 + root.val)\n",
    "            dfs(root.right, pre * 10 + root.val)\n",
    "        dfs(root, 0)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            self.findPath(root, 0)\n",
    "            return self.res\n",
    "    def findPath(self, root, temp):\n",
    "        if not root:\n",
    "            return 0\n",
    "        temp = temp*10 + root.val\n",
    "        if not root.left and not root.right:\n",
    "            self.res += temp\n",
    "        else:\n",
    "            self.findPath(root.left, temp)\n",
    "            self.findPath(root.right, temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        global re\n",
    "        re = 0\n",
    "\n",
    "        def dfs(node, record):\n",
    "            global re\n",
    "            if node.left is None and node.right is None:\n",
    "                re += record*10+node.val\n",
    "            if node.left:\n",
    "                dfs(node.left, record*10+node.val)\n",
    "            if node.right:\n",
    "                dfs(node.right, record*10+node.val)\n",
    "\n",
    "        dfs(root, 0)\n",
    "\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root, p):\n",
    "            if not root: return 0\n",
    "            nonlocal ans\n",
    "            p = p*10+root.val\n",
    "            if not root.left and not root.right:\n",
    "                ans += p\n",
    "                return\n",
    "            dfs(root.left, p)\n",
    "            dfs(root.right, p)\n",
    "        \n",
    "        ans = 0\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root,c):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if not root.left and not root.right:\n",
    "                c+=str(root.val)\n",
    "                return int(c)\n",
    "            c+=str(root.val)\n",
    "            return dfs(root.left,c)+dfs(root.right,c)\n",
    "        return dfs(root,'')\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root,sum,num):\n",
    "            if root is None:\n",
    "                return \n",
    "            num=10*num+root.val\n",
    "            if root.left is None and root.right is None:\n",
    "                sum[0]+=num\n",
    "            else:\n",
    "                dfs(root.left,sum,num)\n",
    "                dfs(root.right,sum,num)\n",
    "        \n",
    "        s=[0]\n",
    "        dfs(root,s,0)\n",
    "        return s[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "\n",
    "        def dfs(node, pre_total):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            total = pre_total * 10 + node.val\n",
    "            if not node.left and not node.right:\n",
    "                return total\n",
    "            \n",
    "            else:\n",
    "                return dfs(node.left, total) + dfs(node.right, total)\n",
    "        \n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            def dfs(root, s):\n",
    "                if root.left is None and root.right is None:\n",
    "                    s += str(root.val)\n",
    "                    res.append(s)\n",
    "                    return\n",
    "                elif root.left is None and root.right is not None:\n",
    "                    s += str(root.val)\n",
    "                    dfs(root.right, s)\n",
    "                elif root.left is not None and root.right is None:\n",
    "                    s += str(root.val)\n",
    "                    dfs(root.left, s)\n",
    "                else:\n",
    "                    s += str(root.val)\n",
    "                    dfs(root.left, s)\n",
    "                    dfs(root.right, s)\n",
    "            res = []\n",
    "            s = ''\n",
    "            dfs(root, s)\n",
    "            ans = 0\n",
    "            print(res)\n",
    "            for i in res:\n",
    "                ans += int(i)\n",
    "            return ans\n",
    "  \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        return self._sum(root,0)\n",
    "    \n",
    "    def _sum(self,node,value):\n",
    "        if node==None:\n",
    "            return 0\n",
    "        value=value*10+node.val\n",
    "        if node.left==None and node.right==None:\n",
    "            return value\n",
    "        return self._sum(node.left,value)+self._sum(node.right,value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码已经通过力扣的测试用例，应该可直接成功提交。\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = \"\"\n",
    "        self.res = 0\n",
    "        \n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        # 遍历一遍二叉树就能出结果\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "\n",
    "    # 二叉树遍历函数\n",
    "    def traverse(self, root: TreeNode) -> None:\n",
    "        if not root:\n",
    "            return\n",
    "        # 前序遍历位置，记录节点值\n",
    "        self.path += str(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            # 到达叶子节点，累加路径和\n",
    "            self.res += int(self.path)\n",
    "        # 二叉树递归框架，遍历左右子树\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "\n",
    "        # 后续遍历位置，撤销节点值\n",
    "        self.path = self.path[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            self.findPath(root, 0)\n",
    "            return self.res\n",
    "    def findPath(self, root, temp):\n",
    "        if not root:\n",
    "            return 0\n",
    "        temp = temp*10 + root.val\n",
    "        if not root.left and not root.right:\n",
    "            self.res += temp\n",
    "        else:\n",
    "            self.findPath(root.left, temp)\n",
    "            self.findPath(root.right, temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root: Optional[TreeNode], currVal: int) -> None:\n",
    "            if not root:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            if root.left is None and root.right is None:\n",
    "                ans += currVal * 10 + root.val\n",
    "                return\n",
    "            currVal = currVal * 10 + root.val\n",
    "            dfs(root.left, currVal)\n",
    "            dfs(root.right, currVal)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "\n",
    "        def recur(root, val):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            val = val * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return val\n",
    "            \n",
    "            return recur(root.left, val) + recur(root.right, val)\n",
    "        \n",
    "        return recur(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root: TreeNode, prevTotal: int) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            total = prevTotal * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return total\n",
    "            else:\n",
    "                return dfs(root.left, total) + dfs(root.right, total)\n",
    "\n",
    "        return dfs(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        \n",
    "        self.traverse(root, 0)\n",
    "        return self.res\n",
    "    \n",
    "    # 先序遍历的逻辑更顺\n",
    "    def traverse(self, node, path):\n",
    "        if not node:\n",
    "            return\n",
    "        if not node.left and not node.right:\n",
    "            path = 10 * path + node.val\n",
    "            self.res += path\n",
    "            return\n",
    "        path = 10 * path + node.val\n",
    "        self.traverse(node.left, path)\n",
    "        self.traverse(node.right, path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            self.findPath(root, 0)\n",
    "            return self.res\n",
    "    def findPath(self, root, temp):\n",
    "        if not root:\n",
    "            return 0\n",
    "        temp = temp*10 + root.val\n",
    "        if not root.left and not root.right:\n",
    "            self.res += temp\n",
    "        else:\n",
    "            left = self.findPath(root.left, temp)\n",
    "            right = self.findPath(root.right, temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(node, tot):\n",
    "            if node is None:\n",
    "                return\n",
    "            tot = 10 * tot + node.val\n",
    "            if node.left is None and node.right is None:\n",
    "                nonlocal res\n",
    "                res += tot\n",
    "                return\n",
    "            dfs(node.left, tot)\n",
    "            dfs(node.right, tot)\n",
    "\n",
    "        res = 0\n",
    "        dfs(root, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(node, path_sum):\n",
    "            if not node.left and not node.right:\n",
    "                path_sum = path_sum * 10 + node.val\n",
    "                self.res += path_sum\n",
    "                return \n",
    "            if node.left:\n",
    "                dfs(node.left, path_sum*10 + node.val)\n",
    "            if node.right:\n",
    "                dfs(node.right, path_sum*10 + node.val)\n",
    "            \n",
    "        if not root:\n",
    "            return 0\n",
    "        self.res = 0\n",
    "        dfs(root, 0)\n",
    "    \n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(node, total):\n",
    "            if not node:\n",
    "                return 0\n",
    "            tmp = total + str(node.val)\n",
    "            left = dfs(node.left, tmp)\n",
    "            right = dfs(node.right, tmp)\n",
    "            if not left and not right:\n",
    "                return tmp\n",
    "            return int(left) + int(right)\n",
    "\n",
    "        return int(dfs(root, ''))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        return self.dfs(root, 0)\n",
    "\n",
    "    def dfs(self, root, path):\n",
    "        ### path 当前累计值\n",
    "        if not root:\n",
    "            return 0\n",
    "        path = path * 10 + root.val\n",
    "        if not root.left and not root.right:\n",
    "            return path\n",
    "\n",
    "        return self.dfs(root.left, path) + self.dfs(root.right, path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        def dfs(root, i):\n",
    "            if not root:\n",
    "                return 0\n",
    "            v = root.val + 10 * i\n",
    "            if not root.left and not root.right:\n",
    "                return v\n",
    "            else:\n",
    "                return dfs(root.left, v) + dfs(root.right, v)\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        def dfs(root: Optional[TreeNode], prev: int) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            total = prev * 10 + root.val\n",
    "            if not root.left and not root.right:\n",
    "                return total\n",
    "            else:\n",
    "                return dfs(root.left, total) + dfs(root.right, total)\n",
    "        \n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        if root is None:\n",
    "            return 0\n",
    "        else:\n",
    "            self.findPath(root, 0)\n",
    "            return self.res\n",
    "    def findPath(self, root, temp):\n",
    "        if not root:\n",
    "            return 0\n",
    "        temp = temp*10 + root.val\n",
    "        if not root.left and not root.right:\n",
    "            self.res += temp\n",
    "        else:\n",
    "            left = self.findPath(root.left, temp)\n",
    "            right = self.findPath(root.right, temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: TreeNode) -> int:\n",
    "        \n",
    "        self.ret = 0\n",
    "\n",
    "        def dfs(root, his):\n",
    "            if not root.left and not root.right:\n",
    "                print(root.val, his, root)\n",
    "                self.ret += int(his) \n",
    "                return   \n",
    "            if root.left:\n",
    "                dfs(root.left, his + str(root.left.val))\n",
    "            if root.right:\n",
    "                dfs(root.right, his + str(root.right.val))\n",
    "        \n",
    "        dfs(root, str(root.val))\n",
    "        return self.ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
